package xyz.scootaloo.code.verify

/**
 * 在一个二维数组中搜索所有满足条件的结果, 返回所有结果的坐标(List)
 *
 * @author flutterdash@qq.com
 * @since 2021/11/3 13:31
 */

fun searchInScope(world: Array<CharArray>, target: Char): List<Pair<Int, Int>> {
    val row  = world.size
    val col = world[0].size

    val directs = arrayOf(-1 to 0, 0 to 1, 1 to 0, 0 to -1)
    val cache = HashSet<Pair<Int, Int>>()

    fun isOutOfBound(pos: Pair<Int, Int>): Boolean {
        if (pos.first < 0 || pos.first > row - 1) return true
        if (pos.second < 0 || pos.second > col - 1) return true
        return false
    }

    fun isOnBound(pos: Pair<Int, Int>): Boolean {
        if (pos.first == 0 || pos.first == row - 1) return true
        if (pos.second == 0 || pos.second == col - 1) return true
        return false
    }

    fun dfs(r: Int, c: Int, path: MutableList<Pair<Int, Int>>): Boolean {
        if (isOnBound(r to c))
            return false

        path.add(r to c)
        cache.add(r to c)
        var flag = true

        for (d in directs) {
            val nextPos = (r + d.first) to (c + d.second)
            if (cache.contains(nextPos))
                continue
            if (isOutOfBound(nextPos))
                continue
            if (world[nextPos.first][nextPos.second] != target)
                continue

            if (!dfs(nextPos.first, nextPos.second, path))
                flag = false
        }
        return flag
    }

    for (r in 0 until row) {
        for (c in 0 until col) {
            val ch = world[r][c]
            if (ch == target && !cache.contains(r to c)) {
                val path = ArrayList<Pair<Int, Int>>()
                if (dfs(r, c, path)) {
                    print(r to c)
                    print(" => ")
                    println(path)
                } else {
                    println("errors -> $path")
                }
            }
        }
    }
    return emptyList()
}

val example = arrayOf(
    charArrayOf('A', 'A', 'A', 'A'),
    charArrayOf('A', 'A', 'B', 'A'),
    charArrayOf('A', 'B', 'B', 'A'),
    charArrayOf('B', 'A', 'A', 'B')
)

fun main() {
    searchInScope(example, 'B')
}
